package algorithm_demo.demo04;

/**
 * @author Api
 * @date 2023/2/15 22:54
 */
public class Code04_MinLight {
    /*
    * 给定一个字符串str，只由'X'和'.'两种字符构成；
    * 'X'表示墙，不能放灯，也不需要点灯；
    * '.'表示居民点，可以放灯，需要点亮
    * 如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮
    * 返回如果点亮str中所有需要点亮的位置，至少需要几盏灯
    * */

    /*贪心算法，总是在当前步做最优解*/
    public static int minLight(String road) {
        char[] str = road.toCharArray();
        int index = 0;
        int light = 0;
        while (index < str.length) {
            if (str[index] == 'X') {//当前为墙，不能放灯
                index++;
            } else {
                light++;
                if (index + 1 == str.length) {
                    break;
                } else {
                    if (str[index + 1] == 'X') {
                        index += 2;
                    } else {
                        index += 3;
                    }
                }
            }
        }
        return light;
    }
}
